When constructing large scale switches, it is often advantageous to use smaller building blocks in order to increase the scalability of the switch. One known building block with good scalability is multistage switches. A multistage switch is in turn built up by smaller switching elements, which are arranged in stages. Each switching element has a number of input ports and a number of output ports. For some of these multistage switches, output ports of a switching element in one stage are connected to input ports of different switching elements in a next stage. Thus, if there are at least three stages in such a multistage switch, there is more than one path from an input port of a switching element in the first stage to an output port of a switching element in the last stage. This type of multistage switches is referred to as multipath multistage switches herein. By using the features of a multipath multistage switch, it is possible to create a so-called non-blocking multistage switch.
Early prior art non-blocking multistage switches are built up of an equal number of switching elements in each stage and connections between each switching element in one stage and each switching element in a next stage. However, for these non-blocking multistage switches there are some limitations with respect to the channels that are to be switched. For example, if so called multirate is introduced, i.e. different channels that are to be switched have different bandwidths, the non-blocking properties will not be preserved unless changes are made to the structure of the switch and/or the way resources are allocated in the switch. The same goes for the introduction of multicast, where one channel should be switched from one input port to more than one output port.
Prior art multipath multistage switches for switching time division multiplexed bitstreams are built up of time and space switching elements in the first and the last stage and space switching elements in intermediate stages, i.e. stages in-between the first and the last stage. Thus, when establishing a channel between an input port and an output port in such a multipath multistage switch, there are two conditions that need to be satisfied. First, the bandwidth must be available on all connections and in all switching elements on a path between the input port and the output port. Second, since the intermediate switching elements only perform space switching, the bandwidth must be available in corresponding time slots of frames of bit streams on all connections on the path between the input port and the output port. This limits the freedom of establishing channels through the switch and makes the control of the establishment of channels complex, especially in the case of multicast. In prior art multistage switches the freedom is usually increased by introducing time expansion and/or an increase of the number of space switching elements in intermediate stages (see for example Soung C. Liew et al “Blocking and Nonblocking Multirate Clos Switching Networks, IEEE/ACM Transactions on Networking, Vol. 6, No. 3, June 1998). Time expansion means that the data transfer rate is higher within the multipath multistage switch than it is on input ports and output ports of the multipath multistage switch. However, the introduction of time expansion and/or an increase of the number of switching elements in intermediate stages will lead to an increased demand of accuracy in synchronisation or an increased complexity of the multipath multistage switch, respectively. This will make the switch costly. For a multirate switch the blocking might be severe due to the inability to fit in large channels when several links are utilised. In the extreme case it can be shown that the time expansion or the number of intermediate stages required might go to infinity if the channel can be of any size.
This problem of limited freedom of establishing channels through the switch and thus, the complex control of the establishment of channels in prior art multipath multistage switches, is, as mentioned above, especially severe in the case of multicast. This is due to the fact that, in the case of multicast, it is preferable that the copying of the data pertaining to a channel is made in as late a stage as possible in order to save bandwidth in the earlier stages. In prior art multipath multistage switches it is difficult to find one switching element in an intermediate stage that can carry the multicast channel from one input port to a number of output port since the data pertaining to the channel must be copied into corresponding time slots in frames of outgoing bitstreams at the output ports as they were received at the input port.
Furthermore, the introduction of multirate networks gives rise to problems with the allocation of resources to channels in multipath multistage switches. For example, when resources are allocated to channels these resources must be allocated so that fragmentation of the resources is avoided. Fragmentation may give rise to a situation where a new channel is to be established, for which the resources are available in the switch, but since resources are fragmented, the resources are not available on one path through the switch. In some prior art switches fragmentation is avoided by the application of methods for optimising the resource allocation of the channels (see for example Soung C. Liew et al “Blocking and Nonblocking Multirate Clos Switching Networks, IEEE/ACM Transactions on Networking, Vol. 6, No. 3, June 1998). However, even though the resource allocation is optimised when the channels are established, fragmentation may still arise. This is due to the fact that, over time, new channels will be established and old channels will be terminated. In some prior art multipath multistage switches, this is solved by moving channels that are already established so that the resources are available on one path through the switch. The methods for optimising the bandwidth allocation of the channels and the moving of channels that are already established, will require information of the state of each switching element of the multipath multistage switch. The complexity of moving channels grows with the switch since global knowledge is required. Thus, a problem with these prior art multipath multistage switches is that the complexity of the resource allocation will be high. Another problem is that, even though the resource allocation is optimised and already established channels are moved, the situation described above, where a new channel cannot be established even though the resources are available in the switch, may still occur.
Furthermore, in some prior art switches resource fragmentation is alleviated by the introduction of time expansion and/or an increase of the number of switching elements in intermediate stages. However, the introduction of time expansion and/or an increase of the number of switching elements in intermediate stages will lead to an increased demand of accuracy in synchronisation or an increased complexity of the multipath multistage switch, respectively. Furthermore, for multicast of multirate channels, the introduction of time expansion and/or an increase of the number of switching elements in intermediate stages the switch will only decrease the level of blocking, i.e. the switch will not be non-blocking.